#pragma once

#include <vector>
#include <map>
#include <tuple>
#include <iostream>

using namespace std;

// Grafo implementado utilizando matriz de incidência
template<typename V = char, typename E = char>
class IncidenceMatrixGraph
{
  struct Elem
  {
    bool active;

    E value;

    Elem():
    active(false)
    {
    }

    Elem(bool active, const E &value):
    active(active),
    value(value)
    {
    }
    
    operator bool() const
    {
      return active;
    }
  };

  vector<vector<Elem>> _matrix;

  // guardo o valor dos nós numa estrutura externa, com acesso em O(1)
  vector<V> _nodeValues;

  int _nodeIndex;
  int _edgeIndex;

public:

  IncidenceMatrixGraph(int n):
  _nodeIndex(0),
  _edgeIndex(0),
  // o número máximo de arestas é n^2 / 2 
  _matrix((n*n)/2)
  {
    for (int i = 0; i<_matrix.size(); i++) {
      _matrix[i].reserve(n);
      _matrix[i].resize(n);
    }

    _nodeValues.reserve(n);
  }
  
  int addNode(const V &value = V())
  {
    _nodeValues.push_back(value); 
    return _nodeIndex++;
  }

  const V &getNodeValue(int n) const
  {
    return _nodeValues[n];
  }

  int countNodes() const
  {
    return _nodeIndex;
  }

  int getNodeDegree(int node) const
  {
    int d = 0;
    for (int i = 0; i < _edgeIndex; i++)
    {
      if (_matrix[i][node]) {
        d++;
      }
    }
    return d;
  }

  int countEdges() const
  {
    return _edgeIndex;
  }

  bool addEdge(int node1, int node2, const E &value = E())
  {
    if (node1 >= _nodeIndex || node2 >= _nodeIndex || node1 == node2) {
      return false;
    }

    _matrix[_edgeIndex][node1] = {true,value};
    _matrix[_edgeIndex][node2] = {true,value};

    _edgeIndex++;

    return true;
  }
  
  bool areNodesAdjacents(int node1, int node2)
  {
    int i = 0;

    for (;i < _edgeIndex && !(_matrix[i][node1] == _matrix[i][node2] && _matrix[i][node1]); i++);

    return i < _edgeIndex;
  }
  
  const E &getEdgeValue(int node1, int node2) const
  {
    for (int i = 0; i < _edgeIndex; i++) {
      if (_matrix[i][node1] && _matrix[i][node2]) {
        return _matrix[i][node1].value;
      }
    } 
    // retorna nada, undefined.
    // FIXME: lançar exceção indicando erro
  }

  vector<int> getAdjacentNodes(int node) const
  {
    vector<int> v;
    for (int i = 0; i < _edgeIndex; i++) {
      // se incide numa determinada aresta, 
      // procura pelo único outro vértice que tbm incide nela 
      if (_matrix[i][node]) {
        for (int j=0; j<_nodeIndex; j++) {
          if (j != node && _matrix[i][j]) {
            v.push_back(j);
            break;
          }
        }
      }
    } 
    return v;
  }
};
